package LeetcodeTest_twenty_nine;
//526.优美的排列

import java.util.ArrayList;

public class countArrangement
{
    public static void main(String[] args)
    {
        System.out.println(solution.countArrangement(3));
    }
}
class solution
{
    public static int count=0;
    public static int countArrangement(int N)
    {
        ArrayList<Integer> temp=new ArrayList<>();
        backtrace(N,0,temp);
        int result=count;
        count=0;
        return result;
    }
    public static void backtrace(int N,int index, ArrayList<Integer> temp)
    {
        ArrayList<Integer> answer=new ArrayList<>(temp);
        if(answer.size()==N)
        {
            count++;
            return;
        }
        else
        {
            for(int i=1;i<=N;i++)
            {
                if(!answer.contains(Integer.valueOf(i)) && ((index+1)%i==0||i%(index+1)==0))
                {
                    answer.add(i);
                    backtrace(N,index+1,answer);
                    answer.remove(answer.size()-1);
                }
                else
                    continue;
            }
        }
    }
}